﻿using System;
using System.Collections.Generic;
using System.Diagnostics.Metrics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//先暴力一下
//
public class Solution347
{

    class Node347
    {
        public int key;
        public int count;
        public Node347 next;
        public Node347 pre;
        public Node347(int key = 0, int count = 0, Node347 next = null, Node347 pre = null)
        {
            this.key = key;
            this.count = count;
        }

    }
    //使用单链表维护一个排序的表
    //提高排序效率，可以使用堆进行存
    //牛逼，使用链表存排序，边遍历边排序，不过时间复杂度是o（n2）
    public int[] TopKFrequent2(int[] nums, int k)
    {
        Dictionary<int, Node347> counts = new Dictionary<int, Node347>();
        Node347 dummyHead = new Node347(-1, int.MaxValue);
        dummyHead.pre = dummyHead;
        dummyHead.next = dummyHead;
        for (int i = 0; i < nums.Length; i++)
        {
            if (counts.TryGetValue(nums[i], out Node347 node))
            {
                node.count++;
                Console.WriteLine(node.count);
                //调整队伍

                while (node.count > node.pre.count)
                {
                    //交换
                    swap(node, node.pre);

                }


            }
            else
            {
                Console.WriteLine("新加入数字" + nums[i]);
                Node347 newNode = new Node347(nums[i], 1);
                counts[nums[i]] = newNode;
                //加入队尾
                newNode.pre = dummyHead.pre;
                dummyHead.pre.next = newNode;
                dummyHead.pre = newNode;
                newNode.next = dummyHead;

            }

        }
        int[] res = new int[k];
        Node347 cur = dummyHead.next;


        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine("数字是：" + cur.key + "   数量是：" + cur.count);



            if (i < k)
            {
                res[i] = cur.key;
            }
            cur = cur.next;

        }
        return res;

    }

    private void swap(Node347 curNode, Node347 preNode)
    {
        curNode.pre = preNode.pre;
        curNode.pre.next = curNode;
        preNode.next = curNode.next;
        preNode.next.pre = preNode;

        preNode.pre = curNode;
        curNode.next = preNode;


    }
    //桶排序？
    public int[] TopKFrequent3(int[] nums, int k)
    {
        //先把频率存好
        Dictionary<int, int> counts = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            if (counts.TryGetValue(nums[i], out int count))
            {
                counts[nums[i]]++;
            }
            else
            {
                counts[nums[i]] = 1;
            }


        }

        IList<IList<int>> list = new List<IList<int>>();
        for (int i = 0; i <= nums.Length; i++)
        {
            list.Add(new List<int>());
        }

        //这个数组的大小是固定的（最大就是整个数组都是一个数字），但是想使用数组代替哈希不可能，因为数的范围不确定
        foreach (var pair in counts)
        {
            int key = pair.Key;
            int count = pair.Value;
            list[count].Add(key);


        }
        int[] res = new int[k];
        int index = 0;
        for (int i = list.Count - 1; i >= 0; i--)
        {

            for (int j = 0; j < list[i].Count; j++)
            {

                if (index < k)
                {
                    res[index++] = list[i][j];
                }


            }

        }
        return res;
    }
    //堆排序？小根堆排序
    public int[] TopKFrequent(int[] nums, int k)
    {  //先把频率存好
        Dictionary<int, int> counts = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            if (counts.TryGetValue(nums[i], out int count))
            {
                counts[nums[i]]++;
            }
            else
            {
                counts[nums[i]] = 1;
            }


        }
        int[] heap = new int[k];//index是树标，haep[i]是key，比较的时候使用count
                                //key可能是-1

      
        
        List<int> list = new List<int>();
        foreach (int key in counts.Keys)
        {
            list.Add(key);
        }
        for (int i = 0; i < k; i++)
        {
            heap[i] = list[i];
            
        }
        

                Console.WriteLine("建堆");
                MakeSmallHeap(heap, counts);//煎堆之后字典变化了？

        for (int i = k; i < list.Count; i++)
        {

            int key=list[i];
            Console.WriteLine(key + "=" + counts[key]);
            Console.WriteLine(heap[0] + "   heap[0]=" + counts[heap[0]]);
                if (counts[key] > counts[heap[0]])
                {//次数大于最小的，进堆

                    Console.WriteLine("次数大于最小的" + key + "=" + counts[key]);
                    heap[0] = key;
                    //调整
                    AdjustSmallHeap(heap, 0, heap.Length, counts);
                }
                

        }
       

        return heap;//这里面就是最多的k个
    }

   //public void MyHeapSort(int[] nums)
   // {
   //     int len=nums.Length;
   //     MakeSmallHeap(nums);
   //     //最大值在nums[0]的位置，输出之后交换到最后
   //     for (int i = nums.Length-1; i>0; i--)
   //     {
   //         Console.WriteLine(nums[0]);

   //         Swap(nums, i,0);
   //         //调整，把最大的放到nums[0]
   //         len--;//最后一个不要调整了，不然又会升上来
   //         AdjustSmallHeap(nums, 0,len);
   //     }


   // }
    private void MakeSmallHeap(int[] heap, Dictionary<int, int> counts)
    {

        for (int i = heap.Length / 2; i >=0; i--)
        {
            AdjustSmallHeap(heap, i, heap.Length, counts);
        }
    }

    private void AdjustSmallHeap(int[] heap, int i,int len, Dictionary<int, int> counts)
    {
       
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;

        if (leftChild < len && counts[heap[leftChild]] < counts[heap[i]])
        {
            Swap(heap, leftChild, i);
            AdjustSmallHeap(heap, leftChild, len, counts);
        }
        if (rightChild < len && counts[heap[rightChild]] < counts[heap[i]])
        {
            Swap(heap, rightChild, i);
            AdjustSmallHeap(heap, rightChild, len, counts);
        }


    }
    private static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    }
}
    class Program347
{
    static void Main347(string[] args)
    {
        //int[] nums = [4, 1, -1, 2, -1, 2, 3];
        int[] nums = [5, 3, 1, 1, 1, 3, 5, 73, 1];
        int k = 3;
        //int[] nums = [1];
        //int k = 1;
        int[] num = { 3, 2, 1, 5, 6, 4 };
        Solution347 solution347 = new Solution347();
        int[] res = solution347.TopKFrequent(nums, k);
        //solution347.MyHeapSort(num);
        
        for (int i = 0; i < k; i++)
        {
            Console.WriteLine(res[i]);
        }
    }

}